package leetcode.递归回溯BFSDFS;

/**
 * 437. 路径总和 III
 *
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 * 找出路径和等于给定数值的路径总数。
 * 路径不需要从根节点开始，也不需要在叶子节点结束，
 * 但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 * 解法：使用到了双重递归思路
 * 就是，先检查 root 节点，看是否能找到一条路径，找不到的话就从 root.left 再开始找一遍
 */
public class Test437路径总和III {


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 所遍历的路径不要求从root开始到叶子节点结束
     * 所遍历的路径可能包含负数
     * 采用 sum-node.val 的方式往下找节点是比较好的处理方式，但是，可能存在
     * 所遍历的路径里面没有一个 node 的值等于传入的 sum
     */

    // 在以 root 为根节点的树中找路径和为 sum 的路径，并返回路径数量
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        res += findNode(root, sum);
        // 然后假设所遍历的路径里面不包含当前当前节点，再次寻找
        res += pathSum(root.left, sum);
        res += pathSum(root.right, sum);
        return res;
    }

    // 在以 node 为根节点的树中找路径和为 sum 的路径，并返回路径数量
    // 这是在当路径里面包含传入节点的 val 时的情况
    public int findNode(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        int res = 0;
        if (node.val - sum == 0) {
            res += 1;
        }
        // 上面没有即时返回，排除负数带来的影响
        res += findNode(node.left, sum - node.val);
        res += findNode(node.right, sum - node.val);
        return res;
    }
}
